import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-07-30
 * Time: 16:35
 */
public class MergeSort {

    /**
     * 归并排序
     * 时间复杂度 : O(N * logN ) 高度 logN 每一层有 N 个数
     * 空间复杂度 : 由于是递归, 递归左数组时为 O(logN), 递归右边是左边已经回收, 同样为 O(logN), 但是由于创建临时数组最终复杂度为 O(N)
     * 稳定性 : 稳定的排序
     *
     * @param array 排序的数组
     * @param start 数组的左边界
     * @param end   数组的右边界
     */
    public void mergeSort(int[] array, int start, int end) {

        // 先进行分组后再合并排序
        partition(array, start, end);

    }

    /**
     * 分治思想进行分组
     *
     * @param array 要进行分组的数组
     * @param left  数组的左边界
     * @param right 数组的右边界
     */
    private void partition(int[] array, int left, int right) {
        // 只有一个元素不需要在划分数组
        if (left == right) {
            return;
        }

        int midIndex = left + ((right - left) >> 2);

        // 划分左数组
        partition(array, left, midIndex);

        // 划分右数组
        partition(array, midIndex + 1, right);

        // 将两个数组归并排序后返回
        merge(array, left, midIndex, right);
    }

    /**
     * 归并数组
     *
     * @param array    排序的原数组
     * @param left     要合并的两个子数组的左子数组的左边界
     * @param midIndex 左边界和右边界的中间值
     * @param right    要合并的两个子数组的右子数组的右边界
     */
    private void merge(int[] array, int left, int midIndex, int right) {
        int[] tmpArray = new int[right - left + 1];
        int k = 0;
        int s1 = left;
        int e1 = midIndex;
        int s2 = midIndex + 1;
        int e2 = right;

        while (s1 <= e1 && s2 <= e2) {
            // TODO : 此处条件如果不加等号则会变成不稳定的排序
            if (array[s1] <= array[s2]) {
                tmpArray[k++] = array[s1++];
            } else {
                tmpArray[k++] = array[s2++];
            }
        }

        // 两个数组都有可能先走完或者同时走完, 需要进行做出判断
        while (s1 <= e1) {
            // 子数组 2 先走完, 将 1 数组中的其他元素 ( 本身有序 ) 加入到 tmpArray 中.
            tmpArray[k++] = array[s1++];
        }

        while (s2 <= e2) {
            tmpArray[k++] = array[s2++];
        }

        // 最终将 tmpArray 中元素拷贝到 array 中
        int i = 0;
        for (int x : tmpArray) {
            // i + left
            // 如果只是 i++, 那么当右边数组归并后, 不是从 0 开始的, 而是从 midIndex + 1 开始的, 否则就会一直覆盖从 0 开始
            // i + left 防止右边子数组赋值会原来数组时从零开始覆盖前面左边子数组数据
            array[i + left] = x;
            i++;
        }
    }

    /**
     * 非递归归并排序
     *
     * @param array 排序数组
     */
    public void mergeSort(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i++) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                // 矫正 mid 防止越界
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                // 矫正 right 防止越界
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = {10, 6, 7, 1, 33, 22, 3, 9, 4, 2};
        mergeSort.mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}
